#pragma once

#include<stdio.h>
#include<stdlib.h>

#define HASH_TABLE_NUM 10

/*
* 开放地址解决冲突的哈希表
*/
typedef struct HashTableOpenSite{
	int num;
	char* data;
}HashOpen;

HashOpen* InitHashTableOpenSite(){
	HashOpen* hashTable = (HashOpen*)malloc(sizeof(HashOpen));
	hashTable->data = (char*)malloc(sizeof(char) * HASH_TABLE_NUM);
	hashTable->num = 0;

	for (int i = 0; i < HASH_TABLE_NUM; i ++) {
		hashTable->data[i] = 0;
	}

	return hashTable;
}

/*
* 计算哈希值, 直接通过数据对哈希表的长度取余, 获取数据所在位置
*/
int HashFunc(char data) {
	return data % HASH_TABLE_NUM;
}

/*
* 线性探测
* 冲突时:
* f(data) = f(f(data) + count)
*/
void PrintHash(HashOpen* hashTable);
void HashLinearPut(HashOpen* hashTable, char data) {
	int index = HashFunc(data);
	if (hashTable->num == HASH_TABLE_NUM)
		return;

	if (hashTable->data[index] == 0) {
		hashTable->data[index] = data;
	}
	else {
		int count = 0;
		while (hashTable->data[index] != 0) {
			count++;
			index = HashFunc(HashFunc(data) + count);
		}
		hashTable->data[index] = data;
	}
	hashTable->num += 1;
	PrintHash(hashTable);
}

void PrintHash(HashOpen* hashTable) {
	for (int i = 0; i < HASH_TABLE_NUM; i ++) {
		printf("%c -> ", hashTable->data[i]);
	}
	printf("NULL\n");
}

/*
* 查找元素
*/
int FindElement(HashOpen* hashTable, char data) {
	int t_index = HashFunc(data);
	int index = t_index;
	int count = 1;
	while (hashTable->data[index] != data) {
		count++;
		index = HashFunc(index + 1);
		if (index == t_index) {
			return -1;
		}
	}
	printf("比较了 %d 次\t", count);
	return index;
}